ВКЛЮЧИТЬ ЗАПИСЬ!!!
Заполните опросник перед началом занятия: https://docs.google.com/forms/d/e/1FAIpQLSdyc0BGGcf1p2KXmU__kQnaLPMVPcBB1wcHSmZuOo4vKcdbCA/viewform
Упорядочила архитектуру компьютеров
Как сделать такое же большое хранилище, как HDD и такое же быстрое, как SRAM?
Да, флеш-память иногда является кешом для HDD
Есть два типа адресов:
Перевод из физических адресов в виртуальные производится аппаратно в
помощью таблицы (page map), поддерживаемой операционной системой.
Каждый
программа работает в своем контексте.
Page map дает контексту информацию, где находится тот или иной
виртуальный адрес - в основной памяти или на диске и где конкретно.
При переключении контекстов нужно перезагружать page map? Да. Потому что page map один, а контекстов много.
Как они работают?
Куда поместить кэш-память? До MMU или за MMU?
До MMU - кешируем виртуальные адреса, за MMU - кешируем физические адреса.
Ваши варианты?
До MMU:
Плюсы:
Минусы:
За MMU:
Плюсы:
Минусы:
Каждый виртуальный адрес (оффсет страницы) делится на 3 части:
Не ждём окончания работы MMU, сразу начинаем запрашивать данные из кеша. Кэш индексируется виртуальными адресами, а тэгируется физическими. В то время, как MMU использует номер виртуальной страницы, чтобы получить номер физической страницы, кэш использует индексную часть, чтобы найти в кэше адрес. Идет параллельный lookup из кэша и трансляция виртуального адреса в физический через MMU. Затем сравнивается физический адрес от MMU физический тэг от кэша. Если они совпадают, был cache hit. Если нет, то cache miss. Тогда возвращается результат из памяти и записывается в кэш.
Достоинства:
Недостаток:
// Windows
// Возвращает зааллокированный указатель
// VirtualAlloc/VirtualFree
LPVOID VirtualAlloc
(
LPVOID lpAddress, // базовый адрес, если NULL, то система сама выбирает адрес
// При этом адрес округляется до ближайшей границы блока размером 64 Кбайт.
SIZE_T dwSize, // размер
DWORD flAllocationType, // тип аллокации (MEM_COMMIT, MEM_RESERVE, MEM_RESET, ...)
DWORD flProtect // защита (PAGE_NOACCESS, PAGE_GUARD, ...)
);
BOOL VirtualFree
(
LPVOID lpAddress, // адрес
SIZE_T dwSize, // размер памяти
DWORD dwFreeType // тип операции (MEM_DECOMMIT, MEM_RELEASE, ...)
);
// Linux/MacOS
// mmap() / munmap()
// Создает / уничтожает новый маппинг виртуального адресного пространства процесса для использования в приложении
// Если addr == NULL, система сама выбирает адрес, иначе использует заданный адрес как хинт для выделения памяти
// (округляя его до page size)
void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *addr, size_t length);
// Перекрывающиеся маппинги недопустимы и система выбирает следующий свободный вариант, если маппинги перекрываются
| Особенность | Windows | Linux |
|---|---|---|
| Резервирование/коммит | Виртуальная память может быть либо только зарезервирована, либо закоммичена, то есть замаплена (либо в RAM, либо в swap). Маппинг может быть "раскоммичен". | Маппинг всегда "коммитится", необходимости в этом нет |
| Сплит-джойн | Каждый маппинг - это отдельная аллокация, поддерживаемая на уровне OS. Число вызовов VirtualFree() должно соответствовать числу вызовов VirtualAlloc() и туда должен подаваться тот же указатель - нет частичных особождений. | Маппинги можно мержить и сплитить, число вызовов mmap не всегда соответствует числу вызовов munmap |
| Выравнивание | Маппинг всегда начинается с адреса, выровненного по границе 64KB (более точно можно получить allocation granularity через GetSystemInfo). Запрос размера, меньшего, чем 64KB, неоптимален и приводит к неэффективному использованию и фрагментации адресного пространства. | Маппинги могут начинаться с любого адреса, выровненного по размеру страницы (4KB). Можно мапить несколько страниц подряд и все эти маппинги склеятся между собой в один. |
| Количество маппингов | Нет ограничений (однако производительность VirtualAlloc() уменьшится с увеличением к-ва маппингов). | Есть ограничение на число маппингов (65530). Причем точное к-во использованных маппингов узнать нельзя, так как они могут быть склеены или заспличены. Существующие маппинги можно частично размапить |
| Объем | Можно зарезервировать до 128TB виртуального адресного пространства, однако закоммитить можно столько, сколько позволит физическая память и размер свопа. | Поскольку все маппинги изначально закоммичены, размер в виртуальном адресном пространстве гораздо меньше и зависит от размера RAM и swap. Однако, при наихудшем сценарии, когда каждый маппинг содержит только одну страницу лимит будет 255MB (65530 * 4k). |
>xeus-cling-cpp14
#include <iostream>
// C
// Allocates block of size 'size'
// Returns: ptr to allocated block if OK, NULL on error
void *malloc(size_t size);
// Reallocates the given area of memory.
// It must be previously allocated by malloc(), calloc() or realloc()
// and not yet freed with a call to free or realloc. Otherwise, the results are undefined.
void *realloc( void *ptr, size_t new_size );
// Frees block pointed to by 'ptr'
// If ptr is a null pointer, the function does nothing.
// The behavior is undefined if the value of ptr does not equal a value
// returned earlier by malloc(), calloc(), realloc(), or aligned_alloc() (since C11).
void free(void *ptr);
// example
typedef struct {
int member;
} data_t;
data_t* ptr = (data_t*)malloc(sizeof(data_t));
ptr->member = 12345;
std::cout << ptr << "\n";
free(ptr);
// C++
#include <new>
void* operator new ( std::size_t count );
void* operator new[]( std::size_t count );
void* T::operator new ( std::size_t count );
void* T::operator new[]( std::size_t count );
void operator delete ( void* ptr );
void operator delete[]( void* ptr );
void T::operator delete ( void* ptr );
void T::operator delete[]( void* ptr );
// examples
int* ptr = new int[10];
ptr[2] = 1000;
....
delete[] ptr;
class Class {
public:
int member;
};
Class* obj = new Class;
obj->member = 12345;
delete obj;
#include <cstdio>
#include <cstdlib>
// переопределение new и delete
void* operator new(std::size_t sz) {
std::printf("global op new called, size = %zu\n",sz);
return std::malloc(sz);
}
void operator delete(void* ptr) noexcept
{
std::puts("global op delete called");
std::free(ptr);
}
int main() {
int* p1 = new int;
delete p1;
int* p2 = new int[10]; // вызов переопределенного new
delete[] p2;
}
Операторы new и delete могут быть как глобальными, так и у классов, что позволяет использовать специфические аллокаторы для выделения памяти под объекты именно этих классов (оптимизированные для них).
>xeus-cling-cpp14
#include <iostream>
// class-specific allocation functions
struct X {
static void* operator new(std::size_t sz)
{
std::cout << "custom new for size " << sz << '\n';
return ::operator new(sz);
}
static void* operator new[](std::size_t sz)
{
std::cout << "custom new for size " << sz << '\n';
return ::operator new(sz);
}
};
X* p1 = new X;
delete p1;
X* p2 = new X[10];
delete[] p2;
Размещает объект на выделенной извне области памяти Для чего используется:
Недостаток:
>xeus-cling-cpp14
size_t size = 10000;
char* buffer = new char[size];
std::cout << "Buffer: [" << static_cast<const void *>(buffer) << "]\n";
struct MyClass {
int data[100];
MyClass() {std::cout << "constructed [" << this << "]\n";}
~MyClass() {std::cout << "destructed [" << this << "]\n";}
};
MyClass* object1 = new (buffer) MyClass; // вызывает только конструктор, деструктор надо вызвать явно
MyClass* object2 = new (buffer + sizeof(MyClass)) MyClass;
object1->~MyClass();
object2->~MyClass();
delete[] buffer;
По умолчанию для стандартных контейнеров используется std::allocator, который аллокирует/деаллокирует через new/delete. Если вы, например, разработчик игр, вы можете использовать свой аллокатор для конкретного типа данных. Например, в неймспейсе std вектор объявлен так:
template <class T, class Allocator = std::allocator<T>> class vector;
Мы можем использовать другой аллокатор вместо Allocator, и память будет резервироваться им. Например,
#include <iostream>
#include <vector>
void *mymalloc(size_t size) {
return malloc(size); // can be custom
}
void myfree(void *ptr) {
free(p); // can be custom
}
template<typename T>
struct MyAllocatorType
{
typedef T value_type;
};
template <class T>
struct MyAllocator {
MyAllocator() = default;
pointer allocate(size_type n, const void* /*hint*/ = 0) {
return mymalloc(n * sizeof(T));
}
void deallocate(pointer p, size_type /*n*/) {
myfree(p);
}
};
using MyVector = std::vector<int, MyAllocator<int>>;
MyVector vec;
vec.push_back(1); // память аллокируется через mymalloc
Не работаем с сырыми указателями на память:
#include <iostream>
// RAII - в конструкторе аллокируем память, в деструкторе освобождаем, не лучший вариант, но основа для unique_ptr
// обычно RAII используют для гарантированного закрытия файлов, освобождения дескрипторов и проч.
struct Object {
Object(int init_member)
: member(init_member) {
}
int member;
};
template <typename T>
class RAIIWrapper{
public:
template<typename... Args>
RAIIWrapper(Args&&... args)
: m_object(new T(std::forward<Args>(args)...)) {
}
~RAIIWrapper(){
delete m_object;
}
T* operator -> (){
return m_object;
}
private:
T *m_object;
};
// использование:
{
RAIIWrapper<Object> object(1);
object->member = 2;
std::cout << object->member << std::endl;
// object удаляется перед {
}
>xeus-cling-cpp14
#include <memory>
struct Object {
Object(int init_member)
: member(init_member) {
}
int member;
};
// Примеры std::unique_ptr, std::shared_ptr, std::weak_ptr
// unique_ptr - у объекта один хозяин, владение может быть передано другому хозяину
{
auto object = std::make_unique<Object>(1);
object->member = 1;
// object is destroyed before {
}
// shared_ptr - у объекта может быть много владельцев, владение копируется вместе с объектом
{
auto object = std::make_shared<Object>(1);
auto objectCopy = object;
// objectCopy is destroyed
// object is destroyed
}
// weak_ptr
{
auto object = std::make_shared<Object>(1);
// get pointer to data without taking ownership
std::weak_ptr<Object> weak1 = object;
// object is destroyed, we create another instance of Object with member '2'
object = std::make_shared<Object>(2);
// weak1 is expired!
if (auto tmp = weak1.lock())
std::cout << tmp->member << '\n';
else
std::cout << "weak is expired\n";
std::weak_ptr<Object> weak2 = object;
// weak2 points to new object (2)
if (auto tmp = weak2.lock())
std::cout << tmp->member << '\n';
else
std::cout << "weak2 is expired\n";
}
Содержат средства для автоматической аллокации памяти и зачистки аллокированной памяти после того, как работа с объектом закончена. Новые появляющиеся языки обычно используют сборку мусора, потому что это удобно.
Python использует счетчик ссылок для управления памятью
При выходе из scope (конца функции либо уничтожения класса, либо конца py-файла) объект уничтожается. Ссылки на объект хранятся в специальных системных словарях, которые можно получить ф-циями locals(), globals()). Для каждого объекта имеется счетчик ссылок (дополнительный оверхед). Существует механизм слабых ссылок для слежения за "сильными" ссылками и борьбы с reference cycles.
# Python
class Object(object):
def __new__(cls):
print('__new__')
obj = super(Object, cls).__new__(cls)
obj2 = Object()
print(obj)
return obj
def __del__(self):
print('__del__')
def __init__(self):
print('__init__')
self.member = 12345
def test():
obj = Object()
obj.member = 1000
test()
import gc
# Enable automatic garbage collection.
gc.enable()
# Disable automatic garbage collection.
gc.disable()
# Returns true if automatic collection is enabled.
gc.isenabled()
# With no arguments, run a full collection. The number of unreachable objects found is returned.
gc.collect(generation=2)
Работают аналогично std::weak_ptr в С++: слабая ссылка на объект это ссылка, которая не охраняет его от garbage collector: когда остались только слабые ссылки на объект, garbage collection уничтожает объект и память под ним переиспользуется. Основная роль слабых ссылок - реализовывать кэши объектов когда не нужно его поддерживать "живым" только из-за того, что он в кэше. Если используется где-то еще, то он живой, если только в кэше - то удаляется.
import weakref
def checkRef(ref):
obj = ref() # получает объект из слабой ссылки
if obj is None:
# referent has been garbage collected
print ("Object has been deallocated.")
else:
print ("Object is still alive!")
obj = Object()
ref = weakref.ref(obj)
checkRef(ref)
del obj
checkRef(ref)
# Кэш id->объект с использованием слабых ссылок
import weakref
_id2obj_dict = weakref.WeakValueDictionary()
def remember(obj):
oid = id(obj)
_id2obj_dict[oid] = obj
return oid
def id2obj(oid):
return _id2obj_dict[oid]
obj = Object()
obj_id = remember(obj)
print ("obj=", obj_id)
del obj
try:
print ("obj=", id2obj(obj_id))
except KeyError:
print ("No object", obj_id)
В Java в отличие от Python не применяется garbage collecting на основе подсчета ссылок. Объект уничтожается, когда на него перестают ссылаться другие объекты. Рассмотрим garbage collector для Java позже. Обычные ссылки на объекты в Java - это так называемые "сильные" ссылки (StrongRef). Еще есть:
>java
import java.lang.ref.PhantomReference;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;
class Object {
int value;
public Object(int value) {
this.value = value;
}
}
{
// Strong Ref
Object object = new Object(1);
System.out.println("Reference " + object);
}
{
// Soft Ref
SoftReference<Object> softRef = new SoftReference<Object>(new Object(1));
System.out.println("Soft reference " + softRef.get());
}
{
// Weak Ref
int counter = 0;
WeakReference<Object> weakRef = new WeakReference<Object>(new Object(1));
System.out.println("Weak reference " + weakRef.get());
while (weakRef.get() != null)
{
counter++;
System.gc();
System.out.println("Weak reference after " + counter + " loops: " + weakRef.get());
}
}
{
// Phantom Ref
final ReferenceQueue queue = new ReferenceQueue();
PhantomReference<Object> ref = new PhantomReference<Object>(new Object(1), queue);
System.gc();
queue.remove();
System.out.println("Phantom reference deleted");
}
Вопрос к аудитории: есть ли автоматическая аллокация/деаллокация в C и C++?
>xeus-cling-cpp14
// С/С++
int y; // мусор
char *str; // мусор
y = 4; // уже не мусор
std::cout << "stack memory: " << y << "\n";
str = (char*)malloc(100*sizeof(char)); // присвоили указатель на выделенную в heap-е память, в самой памяти мусор
str[0] = 'm'; // 0-й элемент <= m
std::cout << "heap memory: " << str[0] << "\n";
free(str); // освобождаем память в heap-е
// стек освобожается сам, при выходе из main возвращается в исходное состояние
>Java
// Работа со стеком в Java
class Class {
public int member;
Class() {
this.member = 1000; // this.member лежит в классе, но сама 1000 - в heap-е
}
}
{
Class obj = new Class(); // создаем новый экземпляр класса Class в heap-е, но obj лежит на стеке
obj.member = 12345;
} // на выходе из блока member и obj уничтожаются
Карта памяти
Надо выбрать стратегию аллокации. Пример стратегий:
Нужно каким-то образом хранить список свободных блоков. Будем его хранить в свободной области в виде некоей структуры данных (адрес + размер свободного блока). Это может быть связанный список, сортированное дерево либо другая структура данных;
Стратегия должна быть уточнена для практического применения, например, среди подходящих выбирайте блок с минимальным адресом.
Фрагментация - это неспособность аллокатора переиспользовать свободную память. "Дырки", оставшиеся от деаллокации маленьких блоков, нельзя использовать в дальнейшем для аллокации блоков большего размера. Невозможность аллокатора переиспользовать память связана не только с размером и числом "дырок", но и с будущим поведением программы и самого аллокатора. Например, предположим у нас есть 100 свободных блоков размера 10 и 200 свободных блоков размера 20. Память сильно фрагментирована? Это зависит от будущих реквестов. Если будущие реквесты все будут на размер 10, все будет ок, аллокаторы будут использовать блоки на 10 и сплитить блоки на 20. Если же будут реквесты на 30, то это проблема. Если придет 100 реквестов на 10 и 200 на 20, то все зависит от порядка, в котором придут запросы и от решений аллокатора по каждому запросу, куда поместить эти блоки. В данном случае решение best fit работает хорошо.
Фрагментация:
Внешняя фрагментация получается, когда есть свободные блоки, доступные для аллокации, но их нельзя использовать для хранения объектов запрошенных размеров. Внутренняя фрагментация - когда аллокируется подходящий по размеру, но слишком большой блок. При этом остаток просто расходуется впустую, вызывая фрагментацию. Чтобы противостоять внутренней фрагментации, аллокаторы делят блок на несколько частей - после аллокирования части остальное считается новым пустым блоком. Также можно сливать соседние пустые блоки в блоки большего размера.
Фрагментация вызывается "изолированными смертями": соседний блок "умер"->появилась фрагментация. Если блоки "умирают" вместе - фрагментации не происходит. Аллокатор, который может "предсказать", какие объекты "умрут" вместе, может поместить их рядом. Поведение программы влияет на будущую фрагментацию.
Какие будут идеи у аудитории как можно решить задачу наиболее эффективно?
Важно понять, каково поведении реальных программ при аллокации памяти и подобрать соответствующую стратегию аллокатора.
Компилятор C компилирует собственный исходник (аллокирует сразу много, но не надолго)
Расчетная математическая программа (представляет сложное выражение в виде линейной комбинации полиномов) - постоянно и медленно аллокирует объекты
Скрипт на perl-е, обрабатывающий строки (аллокирует сразу много и надолго)
Выводы
Последовательно перебирает список свободных блоков, пока не найдет блок минимального размера, удовлетворяющий запросу; Цель - минимизировать размер неиспользуемого места, убедившись, что фрагменты имеют минимальный допустимый размер. Недостатки - даже при таком подходе мы не можем гарантировать отсутствие фрагментации, плохой worst-case перформанс.
Последовательно перебираем список свободных блоков, пока не найдет первый подходящий блок. Если блок имеет больший размер, чем нужно, он делится на 2 и остаток помещается в список свободных блоков.
Оптимизация first fit - "roving pointer" - бродячий указатель. Запоминается позиция, на которой последний поиск был успешным и следующий поиск начинается с неё.
Используется всегда свободный блок наибольшего размера в надежде избежать образования маленьких неиспользуемых фрагментов, поддерживая остаток наибольшим.
Это массив списков свободных блоков, сгруппированных по размеру. Когда нужен блок определенного размера, выбираем его из соответствующего списка. Вариант: использовать классы размеров, например, группировать по степеням двойки: 2 слова, 2^2, 2^3 и т.д. При запросе округлять вверх. Когда поступает запрос от пользователя на размер ищем соответствующий класс. Если список класса пуст, запрашиваем 1 или 2 страницы у системы, разбиваем на блоки по размеру и добавляем в список блоков.
Достоинства:
Недостатки:
Это
оптимизированный Segregated free lists. Возможен сплит/слияние блоков,
но только со своими buddies (приятелями). 64K c 64K и т.д.
Простая схема - весь heap делится на 2 большие части. Каждая из частей
делится еще на 2. Это позволяет привязать аллокацию к конкретному месту.
В общем массиве списков есть список для каждого размера.
Приближение к best-fit.
Это sequential fits, которые индексируются специальным образом. Например, алгоритм best fit на самобалансирующемся дереве, сортированное по размеру блока. Иногда используется декартово дерево, сортированное по размеру и адресу - Stephenson's Fast Fits allocator.
Используется bitmap (1-бит вектор) для обозначения пустых областей в heap. 1 бит - 1 слово. Используется чаще не в аллокаторах, а в mark-sweep garbage collector-ах (рассматриваем далее).
Аллокатор подстраивается под программу. Заточен под хранение объектов одного типа или размера. С++ имеет возможность создавать отдельный аллокатор для каждого класса. Аллокатор содержит список свободных блоков для данного типа и выдает их при необходимости.
Рассмотрим алгоритмы GC на примере Java. Аллокируем через heap manager память вручную, но освобождается она автоматически.
Дан неориентированный граф G с n вершинами и m рёбрами. Требуется найти в нём все компоненты связности, т.е. разбить вершины графа на несколько групп так, что внутри одной группы можно дойти от одной вершины до любой другой, а между разными группами — пути не существует.
В нашем случае задача упрощается потому что граф - ориентированный и есть фиксированные root-ы.
Как узнать, что именно нужно освобождать? Надо найти объекты, на
которые не ссылаются никакие другие объекты и освободить память, которую
они занимают, причем как можно более эффективно.
Heap - корневой объект + набор объектов.
Каждый объект имеет адрес, размер и набор ссылок на другие объекты (например, их адреса). Никакие два объекта не могут перекрываться. Heap можно представить как направленный граф с вершинами (адрес, размер), ребра - связи между объектами. Надо найти компоненты связности графа. В данном случае , и недостижимы из root-а и должны быть удалены. Нужен набор корневых объектов - это статические переменные и локальные переменные.
| - | - | - | - | - | - | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| - | - | - | - | - | - | - | - | - |
В алгоритме mark-sweep для сбора мусора весь процессинг останавливается. Каждый объект имеет “mark-bit”, который используется для обозначения, посещен ли объект во время сборки мусора.
mark-sweep:
mark(root)
sweep()
mark(o):
if o.mark-bit == 0:
o.mark-bit = 1
for p in o.references():
mark(p)
sweep():
o = 0
while o < N
if o.mark-bit == 1:
o.mark-bit = 0
else:
free(o)
o = o + size(o)
Вопрос: какова алгоритмическая сложность алгоритма mark-sweep?
Достоинства:
Недостатки:
Можно сделать реализацию best fit, first fit или взять любую другую
Заполните опросник в конце занятия: https://docs.google.com/forms/d/e/1FAIpQLSdiatBup4OlDyxR7laLuZl_qKtlJE228W5VrsHnw5GmPf7ZPQ/viewform